This invention is directed to logic design, and more particularly to a method of taking a provided network configuration which may be the result of an automated logic design, and producing therefrom a final network configuration which is the functional equivalent of, and contains fewer connections than, the provided network configuration.
As the complexity of processors has increased, the task of processor logic design has become more difficult. The designer may begin by designing a flow chart or other register-transfer level description to describe the intended operation of the processor, and the processor operation is then simulated from this description in order to ensure that a processor operating in accordance with the flow chart will provide the desired results. A logic implementation is then designed to achieve the operation described in the flow chart, and the resulting logic diagram and original flow chart specification are compared to ensure consistency. Finally, a physical layout is designed in accordance with the logic implementation.
The above process has become significantly more difficult and extraordinarily time consuming with the increasing complexity of the processors being designed. For example, each chip in the 3081 processor available from International Business Machines Corporation includes over 700 circuits capable of performing extremely complex functions.
The flow chart specification of such processor will be quite complex, and even a first attempt at logic diagram implementation will require a substantial amount of time. Further, with increasing processor complexity, the competing interest of gate count and timing constraints become increasingly difficult to satisfy. More particularly, a typical timing constraint may be that a signal must be provided from the output of register A to the input of register B within some predetermined period of time, and the designer may first propose a logic arrangement intended to satisfy this timing constraint while using a minimal number of gates in the circuit path between registers A and B. After timing analysis, however, it may be discovered that the timing constraint has not been satisfied, and the designer must then revise the arrangement of logic between the registers A and B, e.g., by using a larger number of gates to improve the processing speed in that area. Several iterations of design may be required before a logic design is obtained which indeed satisfies all timing constraints with the minimum gate count, and it is therefore not uncommon for the logic design to be quite costly in terms of engineering time.
In view of the above, there has been significant recent activity in the field of automatic logic synthesis. Early work centered on developing algorithms for translating a boolean function into a minimum 2-level network of boolean primitives, and extensions were developed for handling limited circuit fan-in and alternative cost functions. However, because these algorithms employ 2-level minimization, the time required to implement these algorithms increases exponentially with the number of circuits. The use of such algorithms therefore becomes impractical in designing large processors.
Other efforts have attempted to raise the level of specification, e.g., by beginning with behavioral specifications and producing technology-independent implementations at the level of boolean equations. However, the results of such techniques were usually more expensive than manual implementations and did not take advantage of the target technology. For example, the system described by T. D. Friedman et al, in "METHODS USED IN AN AUTOMATIC LOGIC DESIGN GENERATOR (ALERT), " IEEE Trans. Computers C-18, 593-614 (1969), produced implementation for an IBM 1800 processor which required 160% more gates than the manual design for that same processor. Several attempts have been made to produce more efficient logic and to give the designer more control over the implementation, e.g., as described by: H. Schorr, "TOWARD THE AUTOMATIC ANALYSIS AND SYNTHESIS OF DIGITAL SYSTEMS," Ph.D. Thesis, Princeton University, NJ, 1962; C. K. Mestenyi, "COMPUTER DESIGN LANGUAGE SIMULATION AND BOOLEAN TRANSLATION," Technical Report 68-72, Computer Science Department, University of Maryland, College Park, Md. 1968; F. J. Hill and G. R. Peterson, "DIGITAL SYSTEMS: HARDWARE ORGANIZATION AND CONTROL," John Wiley & Sons, Inc., New York, 1973. However, this control has resulted in specification language constraints, so that the specification is at a fairly low level and in closer correspondence with the implementation. This necessarily decreases the advantage of an automated approach, bringing it closer to a system for logic entry rather than logic synthesis.
Several tools have been developed to support the early part of the design cycle, e.g., as described in: M. Barbacci, "AUTOMATED EXPLORATION OF THE DESIGN SPACE FOR REGISTER TRANSFER SYSTEMS," Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, Pa., 1973; D. E. Thomas, "THE DESIGN AND ANALYSIS OF AN AUTOMATED DESIGN STYLE SELECTOR," Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, Pa., 1977; E. A. Snow, "AUTOMATION OF MODULE SET INDEPENDENT REGISTER-TRANSFER LEVEL DESIGN," Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, Pa., 1978; L. J. Hafer and A. C. Parker, "REGISTER-TRANSFER LEVEL DIGITAL DESIGN AUTOMATION: THE ALLOCATION PROCESS," Proceedings of the Fifteenth Design Automation Conference, Las Vegas, Nev., 1978, pp. 213-219; A. Parker, D. Thomas, D. Siewiorek, M. Barbacci, L. Hafer, G. Leive, and J. Kim, "THE CMU DESIGN AUTOMATION SYSTEM--AN EXAMPLE OF AUTOMATED DATA PATH DESIGN," Proceedings of the Sixteenth Design Automation Conference, Las Vegas, Nev., 1978, pp. 73-80. The technique described in the last-cited publication began with a functional description of a machine and produced and implementation in two technologies of the registers, registers operators and their interconnections, but not the control logic to sequence the register transfer. For both TTL and CMOS implementations, however, the automated implementation required substantially more chip area than existing manual designs.
There has also been recent work in logic remapping, i.e., transforming existing implementations from one technology to another. S. Nakamura et al S. Nakamura, S. Murai, C. Tanaka, M. Terai, H. Fujiwara, and K. Kinoshita, "LORES-LOGIC REORGANIZATION SYSTEM," Proceedings of the Fifteenth Design Automation Conference, Las Vegas, Nev., 1978, pp. 250-260; describe a system which will help a designer translate an existing small or medium-scale integration. However, remapping usually involves one-to-one substitution of new technology primitives for old technology primitives, and this often fails to take advantage of simplification which may be available at a higher technology-independent level.
U.S. patent application, Ser. No. 631,364, filed Jul. 16, 1984, entitled, "LOGIC SYNTHESIZER" which application is assigned to the assignee of the present invention sets forth a logic synthesis method in which a register-transfer level flowchart specification is translated in a straightforward manner into a simple AND/OR logic implementation. After expanding the logic implementation to elementary representation and then applying textbook simplifications, the simplified AND/OR implementation is translated to a NAND or NOR implementation, depending on the target technology. The NAND or NOR implementation is then simplified by applying a sequence of simplification transformations which achieve satisfactory results, with the transformation sequence being modified to achieve "normal," "fast" or "small" logic designs. After simplification at the NAND/NOR level, the logic implementation is then translated to the target technology and further simplified. The result is an interconnection of the primitives of the target technology in a language from which automated logic diagrams can be produced in a known manner, and which can be submitted to existing programs for automated placement and wiring and chip fabrication.
According to the present invention, a method is set forth for taking a provided logical design or an original circuit implementation as set forth in U.S. Patent application, Ser. No. 631,364 set forth above, and producing therefrom a final circuit implementation which is the functional equivalent of, and contains fewer corrections than, the original circuit implementation. This is the result of approaching connection minimization globally rather than utilizing local transformation as in the prior art. For example, a semiconductor chip such as a master slice chip which is connected in a given circuit configuration has the number of connections between elements minimized. Stated another way, the idea is to minimize connections between terminals or nodes on the master slice chip. Each of n signals is processed in a circuit configuration sequentially. For each such signal in the given circuit a derived graph is constructed. The minimal cut of the derived graph is found, and this cut is utilized to optimize the circuit. The next signal is processed in the optimized circuit, and this procedure is repeated until all n signals have been processed. The resulting optimized circuit is the functional equivalent of the original circuit, but has fewer connections.